\documentclass[runningheads,a4paper]{llncs}

\usepackage{amsmath}    
\usepackage{amsfonts}
\usepackage{amssymb}

\usepackage{graphicx}


\usepackage[sort&compress]{natbib}
\usepackage{url}
\newcommand{\keywords}[1]{\par\addvspace\baselineskip
\noindent\keywordname\enspace\ignorespaces#1}

\bibliographystyle{unsrt}

\begin{document}

%\mainmatter 

\title{Interacci\'{o}n con entornos din\'{a}micos usando automatas celulares}

%\titlerunning{Interacci\'{o}n con entornos din\'{a}micos usando automatas celulares}

\author{Ramiro Castro\inst{1} \and Juan Pablo Carbajal\inst{2}}

%\authorrunning{R. Castro \& J.P. Carbajal}

\institute{Fa.M.A.F.,Universidad Nacional de C\'{o}rdoba, Argentina\\
\url{http://www.famaf.unc.edu.ar}\\
\email{castro.ramiro@gmail.com}
\and
Laboratorio de Inteligencia Artificial, Universidad de Z\"{u}rich, Suiza\\
\url{http://ailab.ch}\\
\email{carbajal@ifi.uzh.ch}
}

\maketitle


\begin{abstract}
En el presente trabajo describimos un ejemplo de aplicaci\'{o}n de aut\'{o}matas celulares para la simulaci\'{o}n de entornos din\'{a}micos en videojuegos con m\'{u}ltiples agentes aut\'{o}nomos. Los aut\'{o}matas celulares (CA) han sido considerados para la implentaci\'{o}n de fen\'{o}menos f\'{\i}sicos como la propagaci\'{o}n de fuego, olas en superficies de flu\'{\i}dos, ondas de presi\'{o}n, o difusi\'{o}n de gases; sin embargo su uso en videojuegos no es frecuente. Aqu\'{\i} reportamos brevemente la integraci\'{o}n de estas herramientas en sistemas con m\'{u}ltiples agentes, discutimos sus ventajas y desventajas y proveemos algunos ejemplos.

\keywords{cellular automata, swarm intelligence, dynamic environments, characters movement, video games.}
\end{abstract}


\section{Introducci\'{o}n}

En el presente trabajo se muestra una opci\'{o}n de implementaci\'{o}n de \textit{entornos din\'{a}micos} usando \textit{aut\'{o}matas celulares (CA)} junto con algoritmos de \textit{flocking} para el movimiento de grupos de agentes. Los videojuegos de hoy presentan detalles gr\'{a}ficos sin precendentes. Sin embargo la inmersi\'{o}n y la jugabilidad siguen obstaculizados por la simplicidad de los escenarios y la inteligencia de los agentes. Esta \'{u}ltima puede encontrar soluciones en la AI \cite{cog-mod-games,Ram_twentiethinternational,ai-for-comp-games,ai-stim-response,ai-madness} mientras que la primera pueden encontrarla en los CA, aunque con un coste m\'{a}s notable en la performance. Aqu\'{\i} nos concentramos en el acople de ambas soluciones.

Los agentes se animan aplicando t\'{e}cnicas de flocking\cite{Reynolds99steeringbehaviors,modeling-fish} basadas en las reglas de Craig Reynolds\cite{Reynolds87}\footnote{Texto y material disponible en \url{http://www.red3d.com/cwr/}}: \textit{separaci\'{o}n, alineaci\'{o}n y cohesi\'{o}n}. Estas reglas son todas locales y se aplican a cada agente del sistema. El movimiento colectivo observado es un fen\'{o}meno emergente, sin necesidad de comportamientos pre-programados estrictos. Las reglas pueden modificarse seg\'{u}n lo que se desee simular e incluso se pueden agregar reglas como: alejarse de predadores, busqueda de calor, comida, etc.

Los entornos din\'{a}micos son escenarios del videojuego cuyo estado var\'{\i}a siguiendo reglas de evoluci\'{o}n y pueden ser simulados utilizando un CA. El uso de CA para la simulaci\'{o}n de entornos din\'{a}micos ha demostrado alcanzar un alto nivel de realismo \cite{cgarcia-lattice} y la implementaci\'{o}n de algoritmos no agrega complejidad al desarrollo del juego \cite{ca-modeling}. Basta definir la forma de actualizaci\'{o}n del CA que lo simular\'{a} y sus estados. 

Lo que se espera lograr combinando estas t\'{e}cnicas, flocking y CA, es que los agentes puedan interactuar libremente con el entorno din\'{a}mico y que ambos reaccionen de forma natural y flexible. 

\section{Ejemplo de aplicaci\'on}
Para motivar al lector comenzamos nuestra exposici\'on con un ejemplo de aplicaci\'on del sistema propuesto. En la Figura \ref{fig:EjemploX} se muestran capturas de pantallas de un simple simulador programado en Python usando pygame. Los cuadrados rojos representan agentes movi\'{e}ndose en reba\~{n}o que se ven afectados por explosiones en el entorno. Estas explosiones afectan a los agentes impuls\'{a}ndolos con una fuerza que depende de la diferencia de presi\'{o}n y es en el sentido que se expande la onda, como se explica en la secci\'{o}n \ref{sec:Acop}.

\begin{figure}[htb]
\centering
\includegraphics[width=.7\textwidth]{./img/Castro_Carbajal_Fig1.eps}
\caption{\label{fig:EjemploX} Agentes(cuadrados en rojo) siendo afectados por explosiones y una pared (l\'{\i}nea en rojo) que contienen las explosiones. Fig. a)Agentes movi\'{e}ndose en manada libremente mientras ocurre una explosi\'{o}n detr\'{a}s de la pared. Fig. b) Las explosiones rodean la pared pero a\'{u}n no afectan a los agentes. Fig. c) y d) dos explosiones continuas, la primera apenas afecta a los agentes mientras que la segunda los empuja hacia la derecha de la pantalla. En Fig. f) y g) se ve la propagaci\'{o}n de las explosiones anteriores y como \'{e}stas separan a los agentes.}
\end{figure}


\section{Descripci\'{o}n del aut\'{o}mata}
El CA consiste en una matriz de celdas (grilla) y cada celda tiene cuatro vecinos: arriba, abajo, izquierda y derecha. Cada celda es capaz de contener una magnitud real que, en este caso, representa la presi\'{o}n de un fluido. Una perturbaci\'{o}n en el valor de la presi\'{o}n en un punto se propaga a toda la grilla por medio de reglas de actualizaci\'{o}n que definen la evoluci\'{o}n del CA. En la Figura \ref{fig:EjemploX} se puede observar la propagaci\'{o}n de varias singularidades generadas en la grilla, representando explosiones.

Las reglas utilizadas se describen en detalle en una publicaci\'{o}n de Tom Forsyth\cite{ca-modeling} que se destaca por su claridad y se sugiere al lector revisar dicha publicaci\'{o}n para los detalles t\'{e}cnicos. Forsyth mantiene una p\'{a}gina web\footnote{\url{http://home.comcast.net/~tom_forsyth/}} donde el contenido de \cite{ca-modeling} est\'a parcialmente reproducido. En la Figura \ref{fig:CA} mostramos la representaci\'{o}n de objetos est\'{a}ticos en el espacio del juego (considerado {\it continuo}), en el espacio discreto defindo por la grilla del CA. En la figura, las celdas oscuras no son actualizadas por el CA (celdas inertes)y por lo tanto la presi\'{o}n no se propaga a trav\'{e}s de ellas. Las celdas que representan al objeto se seleccionan utilizando el bounding box de cada objeto (la caja de menor \'{a}rea que encierra completamente la base del objeto), es decir, todas las celdas contenindas en el bouding box son consideradas inertes.

\begin{figure}[htb]
\centering
\includegraphics[width=.7\textwidth]{./img/Castro_Carbajal_Fig2.eps}
\caption{\label{fig:CA} Representaci\'{o}n de objetos est\'{a}ticos en el CA. Los objetos en el espacio {\it continuo} se proyectan sobre las celdas del CA. Estas celdas aceptan propiedades de {\it porosidad} que regulan el flujo de material o simplemente no se actualizan, representando objetos s\'{o}lidos.}
\end{figure}

\section{\label{sec:Acop} Acoplamiento con agentes}
Los agentes se mueven en el espacio continuo. La actualizaci\'{o}n de sus posiciones puede hacerse en base a velocidad y fuerza o en base a su posici\'{o}n. Si se basa en velocidades y aceleraciones es necesario implementar un integrador, o en otras palabras, necesitamos un motor de f\'{\i}sica. En la actualidad existen bibliotecas de acceso libre de muy buena calidad: 2D, rescatamos Chipmunk\cite{chip}, por su simplicidad y facilidad de programaci\'{o}n; en 3D, los motores suelen ser m\'{a}s complicados y el emblema de la comunidad libre de hoy es Bullet Physics\cite{bullet}. Es posible prescindir de integradores basados en velocidad e implementar la f\'{\i}sica utilizando \'{u}nicamente las posiciones de los agentes\cite{Müller2007109}. Sin embargo, no tenemos experiencia con estos motores. En este trabajo se eligi\'{o} utilizar movimientos basados en fuerzas. Est\'a elecci\'{o}n facilita el acoplamiento de los agentes con el CA subyacente. Al igual que los objetos est\'{a}ticos, los agentes son representados en el espacio discreto utilizando la proyecci\'{o}n de su bounding box. La fuerza sobre el agente, causada por las ondas de presi\'{o}n fluyendo en el CA, se calcula en base a las diferencias de presi\'{o}n sobre los lados del agente, como se muestra en la Figura \ref{fig:Coupling}. Es decir, la componente horizontal de la fuerza est\'{a} dada por la diferencia entre la presi\'{o}n en los lados izquierdo y derecho. La componente vertical por la diferencia entre las celdas superiores e inferiores. En ecuaciones podemos escribir,

\begin{eqnarray}
p_j &=& \sum_i \vert p_{ij} \vert \quad j=\mathsf{u,d,l,r} \\
\label{eq:dP}\vec{F} &=& \left( p_u - p_d, p_l -p_r \right).
\end{eqnarray}

\begin{figure}[htb]
\centering
\includegraphics[width=.8\textwidth]{./img/Castro_Carbajal_Fig3.eps}
\caption{\label{fig:Coupling} Acoplamiento del CA con los agentes. Las celdas del CA totalmente inclu\'{\i}das en el bounding box del agente se utilizan para calcular la fuerza. Las componentes vertical y horizontal se calculan haciendo la diferencia entre las celdas superiores e inferiores y entre las celdas a la izquierda y a la derecha, respectivamente.}
\end{figure}

\noindent Donde $\mathsf{u,d,l,r}$ indican arriba, abajo, izquierda y derecha, respectivamente. La presi\'{o}n en cada celda se denomina $p_{ij}$, donde el sub\'{i}ndice $i$ recorre las celdas del lado correspondiente. Tomamos el valor abosluto, dado que los valores de $p_{ij}$ pueden ser negativos, de esta manera la suma refleja la "activitad" del CA. Si se omite, el efecto de la presi\'{o}n sobre el agente es menor. El signo de las diferencias en la ecuaci\'{o}n (\ref{eq:dP}) depende de las convenciones utilizadas y pueden variar seg\'un la implementaci\'on.


\section{Discusi\'{o}n y conclusi\'{o}n}

Los CA presentados aqu\'{\i} han sido utilizados en el pasado en proyectos comerciales tales como X-Com\cite{xcom} y Silent Storm\cite{silentstorm} y otros juegos en base a turnos en donde el desempe\~{n}o num\'{e}rico de los algoritmos no es cr\'{\i}tico. En contraste, hemos presentado un esquema de acoplamiento de CA con agentes que se mueven a tiempo real y donde algoritmos eficientes de actualizaci\'{o}n son estrictamente necesarios. Al tiempo de esta publicaci\'{o}n nuestro CA se actualiza de manera no optimizada, especialmente notorio cuando el fen\'{o}meno natural que deseamos simular se propaga muy r\'{a}pidamente, como las explosiones; en\cite{ca-modeling} se brindan soluciones usando octrees o quadtrees. Variaciones al esquema pueden encontrarse en los trabajos de C.G. Bauza\cite{cgarcia-lattice} que han demostrado ser altamente eficientes. Existen otras t\'{e}cnicas empleadas para el simulado de explosiones en videojuegos, entre ellas los {\it sistemas de part\'{\i}culas} \footnote{Art\'{\i}culo online describiendo el algoritmo b\'{a}sico  \url{http://www.gamasutra.com/view/feature/2122/building_a_millionparticle_system.php}}, que han alcanzado un alto nivel de desarrollo.

La topolog\'{\i}a de grilla utilizada en nuestra aplicaci\'{o}n no es necesaria. El automata celular puede implementarse sobre un grafo arbitrario. Esto brinda flexibilidad al modelado del escenario. Trabajos en esta direcci\'{o}n son llevados a cabo en academia, sin embargo la transferencia al mercado de los videojuegos es alarmantemente lenta.

Cabe se\~{n}alar que en videojuegos, la precisi\'{o}n de las simulaciones de fen\'{o}menos f\'{\i}sicos no es una necesidad, simplemente necesitamos captuar el comportamiento cualitativo del fen\'omeno. Este hecho pareciera indicar que una base en f\'{\i}sica o control (para los comportamientos de los agentes) no son requerimientos. Sin embargo, solo el concimiento adecuado de t\'{e}cnicas en dichas disciplinas permite desarrollar simplificaciones efectivas y \'{u}tiles para videojuegos, y a la vez acelera la transferencia de desarrollos.

\section*{Agradecimientos}
Agradecemos a Ezequiel Pozzo por incontables discusiones t\'{e}cnicas. Agradecemos a la comisi\'{o}n organizadora por sus esfuerzos y su apoyo. Tambi\'{e}n queremos agradecer a varios artistas por liberar los derechos de todas sus obras (utilizadas en este manuscrito) y permitir el uso libre y gratuito de ellas.

\bibliography{../referencias}

\end{document}
